package com.alex.statistics.method.clusterAnalysis;

import com.alex.statistics.pojo.request.clusterAnalysis.HierarchicalClusteringRequest;
import com.alex.statistics.pojo.result.clusterAnalysis.HierarchicalClusteringResult;
import org.springframework.stereotype.Service;
import java.util.*;

@Service
public class HierarchicalClusteringService {

    public HierarchicalClusteringResult cluster(HierarchicalClusteringRequest request) {
        long startTime = System.currentTimeMillis();

        // 参数校验
        validateRequest(request);

        // 数据准备
        List<double[]> data = request.getData();
        int n = data.size();
        int k = request.getK();
        double distanceThreshold = request.getDistanceThreshold();
        boolean useThreshold = request.isUseThreshold();

        // 初始化每个点为一个簇（使用内部辅助Cluster类）
        List<InternalCluster> clusters = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            clusters.add(new InternalCluster(i, Collections.singletonList(i)));
        }

        // 构建距离矩阵
        double[][] distanceMatrix = buildDistanceMatrix(data, request.getDistanceMetric());

        // 层次聚类过程
        List<HierarchicalClusteringResult.MergeStep> mergeSteps = new ArrayList<>();
        while (clusters.size() > 1) {
            // 找到最近的两个簇
            double minDistance = Double.MAX_VALUE;
            int index1 = -1, index2 = -1;

            for (int i = 0; i < clusters.size(); i++) {
                for (int j = i + 1; j < clusters.size(); j++) {
                    double distance = getClusterDistance(clusters.get(i), clusters.get(j), distanceMatrix);
                    if (distance < minDistance) {
                        minDistance = distance;
                        index1 = i;
                        index2 = j;
                    }
                }
            }

            // 如果使用距离阈值且距离超过阈值，停止合并
            if (useThreshold && minDistance > distanceThreshold) {
                break;
            }

            // 记录合并步骤（转换为结果类的MergeStep）
            InternalCluster c1 = clusters.get(index1);
            InternalCluster c2 = clusters.get(index2);
            mergeSteps.add(new HierarchicalClusteringResult.MergeStep(
                    c1.getId(),
                    c2.getId(),
                    minDistance
            ));

            // 合并两个簇
            InternalCluster mergedCluster = mergeClusters(c1, c2);

            // 移除旧簇，添加新簇
            if (index2 > index1) {
                clusters.remove(index2);
                clusters.remove(index1);
            } else {
                clusters.remove(index1);
                clusters.remove(index2);
            }
            clusters.add(mergedCluster);

            // 如果达到目标聚类数量，停止合并
            if (!useThreshold && clusters.size() == k) {
                break;
            }
        }

        // 构建最终结果（转换内部簇为结果类的Cluster）
        HierarchicalClusteringResult result = new HierarchicalClusteringResult();
        result.setMergeSteps(mergeSteps);
        result.setFinalClusters(convertToResultClusters(clusters));
        result.setComputeTime(System.currentTimeMillis() - startTime);

        return result;
    }

    // 转换内部簇为结果簇
    private List<HierarchicalClusteringResult.Cluster> convertToResultClusters(List<InternalCluster> internalClusters) {
        List<HierarchicalClusteringResult.Cluster> resultClusters = new ArrayList<>();
        for (InternalCluster ic : internalClusters) {
            resultClusters.add(new HierarchicalClusteringResult.Cluster(
                    ic.getId(),
                    ic.getPointIndices()
            ));
        }
        return resultClusters;
    }

    // 构建距离矩阵
    private double[][] buildDistanceMatrix(List<double[]> data, String distanceMetric) {
        int n = data.size();
        double[][] matrix = new double[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double distance = calculateDistance(data.get(i), data.get(j), distanceMetric);
                matrix[i][j] = distance;
                matrix[j][i] = distance;
            }
        }
        return matrix;
    }

    // 计算两点间距离
    private double calculateDistance(double[] p1, double[] p2, String distanceMetric) {
        switch (distanceMetric.toLowerCase()) {
            case "euclidean":
                return euclideanDistance(p1, p2);
            case "manhattan":
                return manhattanDistance(p1, p2);
            case "cosine":
                return cosineDistance(p1, p2);
            default:
                throw new IllegalArgumentException("不支持的距离度量: " + distanceMetric);
        }
    }

    // 欧氏距离
    private double euclideanDistance(double[] p1, double[] p2) {
        checkDimensionMatch(p1, p2);
        double sum = 0.0;
        for (int i = 0; i < p1.length; i++) {
            sum += Math.pow(p1[i] - p2[i], 2);
        }
        return Math.sqrt(sum);
    }

    // 曼哈顿距离
    private double manhattanDistance(double[] p1, double[] p2) {
        checkDimensionMatch(p1, p2);
        double sum = 0.0;
        for (int i = 0; i < p1.length; i++) {
            sum += Math.abs(p1[i] - p2[i]);
        }
        return sum;
    }

    // 余弦距离
    private double cosineDistance(double[] p1, double[] p2) {
        checkDimensionMatch(p1, p2);
        double dotProduct = 0.0;
        double normA = 0.0;
        double normB = 0.0;

        for (int i = 0; i < p1.length; i++) {
            dotProduct += p1[i] * p2[i];
            normA += Math.pow(p1[i], 2);
            normB += Math.pow(p2[i], 2);
        }

        normA = Math.sqrt(normA);
        normB = Math.sqrt(normB);

        if (normA == 0 || normB == 0) {
            return 1.0;
        }

        return 1.0 - (dotProduct / (normA * normB));
    }

    // 检查维度是否匹配
    private void checkDimensionMatch(double[] p1, double[] p2) {
        if (p1.length != p2.length) {
            throw new IllegalArgumentException("数据点维度不匹配: " + p1.length + " vs " + p2.length);
        }
    }

    // 计算簇间距离（完全 linkage）
    private double getClusterDistance(InternalCluster c1, InternalCluster c2, double[][] distanceMatrix) {
        double maxDistance = Double.MIN_VALUE;
        for (int i : c1.getPointIndices()) {
            for (int j : c2.getPointIndices()) {
                maxDistance = Math.max(maxDistance, distanceMatrix[i][j]);
            }
        }
        return maxDistance;
    }

    // 合并两个簇
    private InternalCluster mergeClusters(InternalCluster c1, InternalCluster c2) {
        List<Integer> mergedIndices = new ArrayList<>(c1.getPointIndices());
        mergedIndices.addAll(c2.getPointIndices());
        return new InternalCluster(Math.min(c1.getId(), c2.getId()), mergedIndices);
    }

    // 参数校验
    private void validateRequest(HierarchicalClusteringRequest request) {
        if (request.getData() == null || request.getData().isEmpty()) {
            throw new IllegalArgumentException("数据不能为空");
        }
        if (request.getData().size() < 2) {
            throw new IllegalArgumentException("数据点数量至少为2");
        }
        // 检查所有数据点维度一致
        int dimension = request.getData().get(0).length;
        for (double[] point : request.getData()) {
            if (point.length != dimension) {
                throw new IllegalArgumentException("所有数据点必须具有相同的维度");
            }
        }
        // 检查距离度量合法性
        if (request.getDistanceMetric() == null ||
                !Arrays.asList("euclidean", "manhattan", "cosine").contains(request.getDistanceMetric().toLowerCase())) {
            throw new IllegalArgumentException("不支持的距离度量，支持: euclidean, manhattan, cosine");
        }
        // 检查聚类数量
        if (!request.isUseThreshold()) {
            if (request.getK() <= 0 || request.getK() >= request.getData().size()) {
                throw new IllegalArgumentException("聚类数量k必须在(0, " + request.getData().size() + ")范围内");
            }
        } else {
            if (request.getDistanceThreshold() < 0) {
                throw new IllegalArgumentException("距离阈值不能为负");
            }
        }
    }

    // 内部辅助类：仅用于服务内部的簇处理
    private static class InternalCluster {
        private final int id;
        private final List<Integer> pointIndices;

        public InternalCluster(int id, List<Integer> pointIndices) {
            this.id = id;
            this.pointIndices = pointIndices;
        }

        public int getId() {
            return id;
        }

        public List<Integer> getPointIndices() {
            return pointIndices;
        }
    }
}